package sword_offer;

/**
 * @ClassName _13RobatMovingCount
 * @Description: 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
 *
 * 一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
 *
 * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 *
 *  
 *
 * 示例 1：
 *
 * 输入：m = 2, n = 3, k = 1
 * 输出：3
 * 示例 2：
 *
 * 输入：m = 3, n = 1, k = 0
 * 输出：1
 * 提示：
 *
 * 1 <= n,m <= 100
 * 0 <= k <= 20
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/11 12:36
 */
public class _13RobatMovingCount {

    public static void main(String[] args) {
//        int m = 2, n = 3, k = 1;
//        int m = 3, n = 1, k = 0;
        int m = 38, n = 15, k = 9;
        int count = new _13RobatMovingCount().movingCount(m, n, k);
        System.out.println(count);
    }

    public int movingCount(int m, int n, int k) {
        // 动态规划：当前这个格子能不能到达的条件：
        // 第一行：左边的格子可到达 && 行坐标和列坐标的数位之和不大于k
        // 第一列：上面的格子可到达 &&左边的格子可到达 && 行坐标和列坐标的数位之和不大于k
        // 其他：(上面的格子可到达 || 左边的格子可到达) && 行坐标和列坐标的数位之和不大于k
        // 空间优化版
        boolean[] dp = new boolean[n];// 数组默认值为boolean
        dp[0] = true;
        int count = 1;
        // 初始化第一层
        for (int i = 1; i < n; i++) {
            if (dp[i - 1] && positionSum(0, i) <= k){
                dp[i] = true;
                count++;
            }
        }
        // 开始迭代，第一列需要特别处理一下
        for (int i = 1; i < m; i++) {
            dp[0] = dp[0] && positionSum(i, 0) <= k;
            if (dp[0])
                count++;
            for (int j = 1; j < n; j++) {
                dp[j] = (dp[j - 1] || dp[j]) && positionSum(i, j) <= k;
                if (dp[j])
                    count++;
            }
        }
        return count;
    }

    public int positionSum(int m, int n){
        int sum = 0;
        while (m != 0){
            sum += m%10;
            m = m/10;
        }

        while (n != 0){
            sum += n%10;
            n = n/10;
        }

        return sum;
    }
}
